class Solution {
    List<String> res = new ArrayList<>();
    StringBuffer stringBuffer = new StringBuffer();

    public List<String> generateParenthesis(int n) {
        dfs(0,0,n);
        return res;
    }

    private void dfs(int left,int right,int n) {
        if(left+right == 2*n) {
            res.add(stringBuffer.toString());
            return;
        }
        if(left<n) {
            stringBuffer.append("(");
            dfs(left+1,right,n);
            stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        }
        if(right<left) {
            stringBuffer.append(")");
            dfs(left,right+1,n);
            stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        }
    }
}